package red.book._2._3;

import red.book._2._1.Example;

public class Quick3way {
	private static void sort(Comparable[] a, int lo, int hi) {
		if(hi <= lo) {
			return;
		}
		int lt = lo, i = lo + 1, gt = hi;
		Comparable v = a[lo];
		while(i <= gt) {
			int cmp = a[i].compareTo(v);
			if(cmp < 0) {
				Example.exch(a, lt++, i++);
			}else if(cmp > 0) {
				Example.exch(a, i, gt--);
			}else {
				i++;
			}
		} // 现在a[lo...lt-1] < v= a[lt..gt] < a[gt+1...hi] 成立。所以只要对相等的2变继续排序即可。
		sort(a, lo, lt -1);
		sort(a, lt, hi);
	}
}
